package utils

import (
	"fmt"
	"math/rand"
)

type SkipListNode[T any, V any] struct {
	Key  *T
	Data *V
	// Next   *SkipListNode[T, V]
	// Levels []*SkipListNode[T, V]
	offset int64
	length int64
}

type SkipList[T any, V any] struct {
	maxLevel  uint32
	levelRate uint32
	cmpFunc   func(*T, *T) int8
	header    *SkipListNode[T, V]
	level     uint32
	Levels    []*SkipListNode[T, V]
	CurPos    int64
}

var K int64

func NewSkipListNode[T any, V any](list *SkipList[T, V], key *T, data *V, dataLevel int) *SkipListNode[T, V] {
	K++
	pos, num := list.alloc(int64(dataLevel))
	return &SkipListNode[T, V]{Data: data, Key: key, offset: pos, length: num}
}

func NewSkipList[T any, V any](maxLevel, levelRate uint32, cmpFunc func(*T, *T) int8) *SkipList[T, V] {
	ret := &SkipList[T, V]{maxLevel: maxLevel, levelRate: levelRate, cmpFunc: cmpFunc, Levels: make([]*SkipListNode[T, V], 1024, 1024)}
	ret.header = NewSkipListNode[T, V](ret, nil, nil, int(maxLevel))
	// header.Levels = make([]*SkipListNode[T, V], maxLevel, maxLevel)
	// for i := 0; i < int(maxLevel); i++ {
	// 	header.Levels[i] = nil //NewSkipListNode[T, V](nil, nil)
	// }
	return ret
}

func (list *SkipList[T, V]) alloc(num int64) (int64, int64) {
	size := len(list.Levels)
	var tmp []*SkipListNode[T, V]
	if list.CurPos+num >= int64(size) {
		if size < 1000000 {
			tmp = make([]*SkipListNode[T, V], size*2, size*2)
		} else {
			tmp = make([]*SkipListNode[T, V], size*125/100, size*125/100)
		}
		tmp = append(tmp, list.Levels...)
		list.Levels = tmp
	}
	offset := list.CurPos
	list.CurPos += num
	return (offset), num
}

func (list *SkipList[T, V]) getNodeLevel(node *SkipListNode[T, V], level int) *SkipListNode[T, V] {
	return list.Levels[node.offset+int64(level)]
}
func (list *SkipList[T, V]) setNodeLevel(node *SkipListNode[T, V], level int, dest *SkipListNode[T, V]) {
	list.Levels[node.offset+int64(level)] = dest
}

func (list *SkipList[T, V]) computeLevel() uint32 {
	var level uint32
	for level < list.maxLevel-1 {
		r := uint32(rand.Intn(100))
		if r >= list.levelRate {
			break
		}
		level++
	}
	return level

}

// func (list *SkipList[T, V]) cmpWrap(k1 unsafe.Pointer, k2 interface{}) int8 {
// 	var kk1 interface{} = k1
// 	if k1 != nil {
// 		// kk1=(*interface{}) k1

// 	}
// 	return list.cmpFunc(kk1, k2)
// }

func (list *SkipList[T, V]) Size() int64 {
	header := list.header
	size := int64(0)
	for list.getNodeLevel(header, 0) != nil {
		size++
		header = list.getNodeLevel(header, 0)
	}
	return size
}

func (list *SkipList[T, V]) Insert(key T, data V) {
	preNodes := make([]*SkipListNode[T, V], list.level+1, list.level+1)
	preNodesStatus := make([]bool, list.level+1)
	level := int(list.level)
	header := list.header
	for level >= 0 {
		for header != nil {
			cmp := list.cmpFunc((header.Key), &key)
			if cmp > 0 {
				break
			}
			preNodes[level] = header
			preNodesStatus[level] = cmp == 0
			// header = header.Levels[level]
			header = list.getNodeLevel(header, level)
		}
		header = preNodes[level]
		level--
	}
	// list.Display()
	if preNodesStatus[0] {
		for idx, status := range preNodesStatus {
			if status {
				preNodes[idx].Data = &data
			}
		}
		return
	}
	dataLevel := int(list.computeLevel())
	// var preNode *SkipListNode[T, V]
	dataNode := NewSkipListNode(list, &key, &data, dataLevel+1)
	// dataNode.Levels = make([]*SkipListNode[T, V], dataLevel+1, dataLevel+1)
	// dataNode.Levels[0] = preNodes[0].Levels[0]
	// preNodes[0].Levels[0] = dataNode
	// fmt.Println(dataLevel)
	for i := 0; i <= dataLevel; i++ {
		if i > int(list.level) {
			list.setNodeLevel(list.header, i, dataNode)
		} else {
			list.setNodeLevel(dataNode, i, list.getNodeLevel(preNodes[i], i))
			list.setNodeLevel(preNodes[i], i, dataNode)
		}
	}
	if list.level < uint32(dataLevel) {
		list.level = uint32(dataLevel)
	}
}

func (list *SkipList[T, V]) Get(key T) (data V, ok bool) {
	// preNodes := make([]*SkipListNode, list.level+1)
	var tmp *SkipListNode[T, V]
	level := int(list.level)
	header := list.header
	for level >= 0 {
		for header != nil {
			if list.cmpFunc((header.Key), &key) > 0 {
				break
			}
			// preNodes[level] = header
			tmp = header
			// header = header.Levels[level]
			header = list.getNodeLevel(header, level)
		}
		// header = preNodes[level].Lower
		header = tmp
		level--
	}
	// tmp := preNodes[0]
	for tmp != nil {
		// fmt.Printf("key:%#v,key:%v\n", tmp.Key, key)
		val := list.cmpFunc((tmp.Key), &key)
		if val == 0 {
			return *tmp.Data, true
		}
		if val > 0 {
			break
		}
		tmp = list.getNodeLevel(tmp, 0)
	}
	return data, false
}

func (list *SkipList[T, V]) Del(key T) {
	preNodes := make([]*SkipListNode[T, V], list.level+1, list.level+1)
	// var tmp *SkipListNode
	level := int(list.level)
	header := list.header
	for level >= 0 {
		for header != nil {
			// fmt.Printf("Del: key:%#v,key:%v\n", header.Key, key)
			if list.cmpFunc((header.Key), &key) >= 0 {
				break
			}
			preNodes[level] = header
			// tmp = header
			header = list.getNodeLevel(header, level)
		}
		header = preNodes[level]
		// header = tmp.Lower
		level--
	}
	i := int(list.level)
	for i >= 0 {
		tmp := preNodes[i]
		// fmt.Printf("Del: tmp:%#v\n", tmp)
		for {
			if tmp == nil || list.getNodeLevel(tmp, i) == nil {
				i -= 1
				break
			}
			// fmt.Printf("Del: key:%#v,key:%v\n", tmp.Next.Key, key)
			val := list.cmpFunc((list.getNodeLevel(tmp, i).Key), &key)

			if val == 0 {
				// tmp.Next = tmp.Next.Next
				// tmp.Levels[i] = tmp.Levels[i].Levels[i]
				list.setNodeLevel(tmp, i, list.getNodeLevel(list.getNodeLevel(tmp, i), i))
				if i == 0 {
					// tmp.Levels[0] = tmp.Levels[0].Levels[0]
					list.setNodeLevel(tmp, 0, list.getNodeLevel(list.getNodeLevel(tmp, 0), 0))
				}
				i -= 1
				break
			}
			// tmp = tmp.Levels[i]
			tmp = list.getNodeLevel(tmp, i)
		}
	}

}

func (list *SkipList[T, V]) Range(keyStart, keyEnd *T, f func(key T, value V)) {
	level := int(list.level)
	header := list.header
	var tmpStart, tmpEnd *SkipListNode[T, V]
	var statusStart bool
	if keyStart == nil {
		tmpStart = list.getNodeLevel(list.header, 0)
	} else {
		for level >= 0 {
			for header != nil {
				cmp := list.cmpFunc((header.Key), keyStart)
				if cmp > 0 {
					break
				}
				statusStart = cmp == 0
				tmpStart = header
				// header = header.Levels[level]
				header = list.getNodeLevel(header, level)
			}
			header = tmpStart
			level--
		}
		if !statusStart {
			// tmpStart = tmpStart.Levels[0]
			tmpStart = list.getNodeLevel(tmpStart, 0)
		}
	}
	level = int(list.level)
	header = list.header
	if keyEnd != nil {
		for level >= 0 {
			for header != nil {
				cmp := list.cmpFunc((header.Key), keyEnd)
				if cmp > 0 {
					break
				}
				// statusEnd = cmp == 0
				tmpEnd = header
				// header = header.Levels[level]
				header = list.getNodeLevel(header, level)
			}
			header = tmpEnd
			level--
		}
	}

	for tmpStart != nil && tmpStart != tmpEnd {
		f(*tmpStart.Key, *tmpStart.Data)
		// tmpStart = tmpStart.Levels[0]
		tmpStart = list.getNodeLevel(tmpStart, 0)
	}
}

func (list *SkipList[T, V]) GetRange(keyStart, keyEnd T) (data []V) {
	level := int(list.level)
	header := list.header
	var tmpStart, tmpEnd *SkipListNode[T, V]
	var statusStart bool
	for level >= 0 {
		for header != nil {
			cmp := list.cmpFunc((header.Key), &keyStart)
			if cmp > 0 {
				break
			}
			statusStart = cmp == 0
			tmpStart = header
			// header = header.Levels[level]
			header = list.getNodeLevel(header, level)
		}
		header = tmpStart
		level--
	}
	level = int(list.level)
	header = list.header
	for level >= 0 {
		for header != nil {
			cmp := list.cmpFunc((header.Key), &keyEnd)
			if cmp > 0 {
				break
			}
			// statusEnd = cmp == 0
			tmpEnd = header
			// header = header.Levels[level]
			header = list.getNodeLevel(header, level)
		}
		header = tmpEnd
		level--
	}
	data = make([]V, 0)
	if statusStart {
		data = append(data, *tmpStart.Data)
	}
	// tmp := tmpStart.Levels[0]
	tmp := list.getNodeLevel(tmpStart, 0)
	for tmp != nil && tmp != tmpEnd {
		data = append(data, *tmp.Data)
		// tmp = tmp.Levels[0]
		tmp = list.getNodeLevel(tmp, 0)
	}
	// if statusEnd {
	data = append(data, *tmpEnd.Data)
	// }

	return data
}

func (list *SkipList[T, V]) Display() {
	fmt.Printf("================list info==============\n")
	fmt.Printf("maxlevel:%d\n", list.maxLevel)
	fmt.Printf("level:%d\n", list.level)
	fmt.Printf("\tdata:\n")
	for i := int(list.maxLevel) - 1; i >= 0; i-- {
		// tmp := list.header.Levels[i]
		tmp := list.getNodeLevel(list.header, i)
		for tmp != nil {
			fmt.Printf("\tdata(%v):%v ", *tmp.Key, *tmp.Data)
			// tmp = tmp.Levels[i]
			tmp = list.getNodeLevel(tmp, i)
		}
		fmt.Printf("\n")
	}
	fmt.Printf("=======================================\n")
}
